package com.myc.subjects.array;

import java.util.Arrays;

/**
 * LeetCode题号：31
 *
 * 下一个排列
 *
 * 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 * 必须 原地 修改，只允许使用额外常数空间。
 *
 * 示例 1：
 * 输入：nums = [1,2,3]
 * 输出：[1,3,2]
 *
 * 示例 2：
 * 输入：nums = [3,2,1]
 * 输出：[1,2,3]
 *
 * 示例 3：
 * 输入：nums = [1,1,5]
 * 输出：[1,5,1]
 *
 * 示例 4：
 * 输入：nums = [1]
 * 输出：[1]
 *
 * 提示：
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 100
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/next-permutation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Xiayigepailie {

    public static void main(String[] args) {
        int[] nums = new int[]{1,4,3,2};
        Xiayigepailie x = new Xiayigepailie();
        x.nextPermutation1(nums);
    }

    /**
     * 方法一：两遍扫描
     * 时间复杂度：O(n)
     * 获取下一次排列的方法为：
     * 从后向前遍历数组，找到第一个升序子序列之后，将升序子序列的第一个值，与后面降序子序列中比他大的最小的值进行交换，然后再将后面的降序子序列升序排列（可以直接翻转数组）
     */
    public void nextPermutation1(int[] nums) {
        int changeIndex = 0;//保存升序子序列的第二个值
        int swapIndex = nums.length - 1;//保存降序子序列中比第一个升序子序列的第一个值大的最小的值

        //从后向前遍历数组，找到第一个升序子序列，并给changeIndex赋值
        for(int i = nums.length - 1; i > 0; i--){
            if(nums[i] > nums[i - 1]){
                changeIndex = i;
                break;
            }
        }

        if(changeIndex > 0){//如果存在升序子序列

            //找到swapIndex
            for(int i = swapIndex; i > changeIndex - 1; i--){
                if (nums[i] > nums[changeIndex]) {
                    swapIndex = i;
                    break;
                }
            }
            swap(nums, swapIndex, changeIndex - 1);//交换
        }

        //反转降序序列（有可能是整个序列）
        reverse(nums, changeIndex);
        //System.out.println(Arrays.toString(nums));
    }


    //官方题解 两遍扫描
    public void nextPermutationOfficial(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    //两数交换方法
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    //反转序列方法
    //通过定义首尾指针，分别交换元素再向中间遍历的方式反转序列
    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

}

/**
 * 总结：
 * 技巧：
 * 1.遇到这里问题先将题意分解为每一步的操作，再按照操作一步步写下来
 * 2.这里的反转序列的方法需要掌握
 */
